import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * @lc app=leetcode.cn id=56 lang=java
 *
 * [56] 合并区间
 *
 * https://leetcode-cn.com/problems/merge-intervals/description/
 *
 * algorithms
 * Medium (38.88%)
 * Likes:    201
 * Dislikes: 0
 * Total Accepted:    34.1K
 * Total Submissions: 87.7K
 * Testcase Example:  '[[1,3],[2,6],[8,10],[15,18]]'
 *
 * 给出一个区间的集合，请合并所有重叠的区间。
 *
 * 示例 1:
 *
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 *
 * 示例 2:
 *
 * 输入: [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 */

// @lc code=start
class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0) {
            return new int[0][0];
        }
        Arrays.sort(intervals, (o1, o2) -> {return o1[0] - o2[0];});

        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);
        int index = 0;
        for(int i = 1; i < intervals.length; i++) {
            int left = list.get(index)[0], right = list.get(index)[1];
            if(right >= intervals[i][0]) {
                list.get(index)[1] = intervals[i][1] > list.get(index)[1] ? intervals[i][1] : list.get(index)[1] ;
            } else {
                index++;
                list.add(index, intervals[i]);
            }
        }
        int[][] res = new int[list.size()][2];
        for(int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
// @lc code=end

